package HashBuck;

import java.util.*;

public class Test2 {
    // 前k个高频词 ：https://leetcode.cn/problems/top-k-frequent-words/description/
    public static  List<String> topKFrequent(String[] words, int k) {
        // 首先计数
        Map<String,Integer> map=new HashMap<>();
        for(String s:words){
            if(map.get(s)==null){
                map.put(s,1);
            }else{
                int val= map.get(s);
                map.put(s,val+1);
            }
        }
        // 其次，找前k个高频词 ,可以建立一个小根堆来进行替换
        PriorityQueue<Map.Entry<String,Integer>>  priorityQueue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                // 如果两字符串出现次数相同，构建大根堆
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });

        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(priorityQueue.size()<k){
                // 将entry中的key传入小根堆
                priorityQueue.add(entry);
            }else{
                Map.Entry<String,Integer> top=priorityQueue.peek();
                if( top.getValue().compareTo(entry.getValue())<0 ){
                    priorityQueue.poll();
                    priorityQueue.add(entry);
                }else if(top.getValue().compareTo(entry.getValue()) == 0 ){
                    // 相等的时候再看他是否满足字典顺序
                    if(top.getKey().compareTo(entry.getKey()) > 0){
                        priorityQueue.poll();
                        priorityQueue.add(entry);
                    }
                }
            }
        }
        List<String> list=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            // 将小根堆中的数据存入链表，存入顺序是小根堆顺序
            list.add(priorityQueue.poll().getKey());
        }
        // 此处将链表倒置，顺序为 出现次数由多到少
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] words={"i","love","leetcode","i","love","coding"};
        List<String> list=topKFrequent(words,3);
        System.out.println();
    }






    // 统计一串字母中，每个数字出现的次数
    public static void statistics(String[] words){
        Map<String,Integer> map=new HashMap<>();
        for(String s:words){
            if(map.get(s)==null){
                map.put(s,1);
            }else{
                int val= map.get(s);
                map.put(s,val+1);
            }
        }
        for (Map.Entry<String,Integer> entry:map.entrySet()){
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
    }

    public static void main02(String[] args) {
        String[] strings={"a","b","c","a","b","b"};
        statistics(strings);

    }





    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    // 随机链表的复制 ： https://leetcode.cn/problems/copy-list-with-random-pointer/description/
    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();

        Node cur=head;
        // 将对应的数据存进去
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur= cur.next;
        }

        // 遍历map, 将要复制的节点连起来
        cur=head;
        for(Map.Entry<Node,Node> entry:map.entrySet()){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur= cur.next;
        }
        return map.get(head);
    }





    // 旧键盘：https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
    private static void Fun(String str1,String str2){
        HashSet<Character> hashSet=new HashSet<>();
        for(char ch:str2.toUpperCase().toCharArray()){
            hashSet.add(ch);
        }
        HashSet<Character> hashSet2=new HashSet<>();
        for(char ch:str1.toUpperCase().toCharArray()){
            if(!hashSet.contains(ch) && !hashSet2.contains(ch)){
                System.out.print(ch);
                hashSet2.add(ch);
            }
        }
    }

    // 宝石与石头 ： https://leetcode.cn/problems/jewels-and-stones/
    public static  int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> hashset=new HashSet<>();
        int count=0;
        for(char i : jewels.toCharArray()){
            hashset.add(i);

        }
        for(char j:stones.toCharArray()){
            if(hashset.contains(j)){
                count++;
            }
        }
        return count;
    }


    // 只出现一次数字: https://leetcode.cn/problems/single-number/description/
    public static  void singleNumber(int[] nums) {
        HashSet<Integer> hashSet=new HashSet<>();
        for (int i:nums) {
            if(!hashSet.contains(i)){
                hashSet.add(i);
            }else{
                hashSet.remove(i);
            }
        }
        for (int i:nums) {
            if(hashSet.contains(i)){
                System.out.println(i);
            }
        }
    }
    public static void main01(String[] args) {
        String str1="7_This_is_a_test";
        String str2="_hs_s_a_es";
        Fun(str1,str2);
    }
}
